This application includes subject matter related to co-pending application entitled: xe2x80x9cSystem For Compression Of Digital Images Comprising Low Detail Areasxe2x80x9d, having U.S. Pat. No. 6,130,630, and the co-pending patent application entitled: xe2x80x9cApparatus And Method For Compressing Huffman Encoded Dataxe2x80x9d, having U.S. Ser. No. 09/179,925, each of which are incorporated by reference herein, assigned to the same assignee as this application, and filed on even date herewith.
This invention relates to the compression of digital images, and more particularly to the compression of a digital image comprising a background.
A digital image is typically displayed or printed in the form of a rectangular array of xe2x80x9cpicture elementsxe2x80x9d or xe2x80x9cprint elementsxe2x80x9d. For purposes of this application, both xe2x80x9cpicture elementsxe2x80x9d and xe2x80x9cprint elementsxe2x80x9d are referred to herein as xe2x80x9cpixelsxe2x80x9d. Digital images are typically represented in a computer by one or more arrays of binary numbers. For example, a monochrome digital image can be represented in a computer by a single array of binary numbers. Each binary number in the array defines a gray-level value for an associated pixel. The position of the binary number in the array describes the spatial location of the pixel.
A color digital image can be represented in a computer by three arrays of binary numbers. Each array (alternatively referred to herein as an xe2x80x9cimage planexe2x80x9d) representing an axis of a suitable color coordinate system in accordance with the well known trichromatic theory. The color of a pixel in the digital image is defined by an associated binary number (defining one of three color components from the color coordinate system) from each array. It is noted that there are many color coordinate systems that can be used to represent the color of a pixel. These color coordinate systems include a xe2x80x9cRed-Green-Bluexe2x80x9d (RGB) coordinate system and a cyan-magenta-yellow (CMY) coordinate system. The former is commonly used in monitor display applications, the latter is commonly used in printing applications. For purposes of this application, each binary number representing a pixel is referred to herein as a xe2x80x9cpixel componentxe2x80x9d or alternatively as a xe2x80x9cpixel component valuexe2x80x9d. In addition, the phrase xe2x80x9cpixel valuexe2x80x9d refers to the value of the number or numbers defining the pixel. It is noted that a pixel value can be defined with reference to the color of the pixel. Thus, a pixel can be said to have a value corresponding to the color or gray-scale level of white. This indicates that the binary number or numbers associated with the pixel has a total value that define the pixel as white.
The amount of data used to represent a digital image can be extremely large. Consider, for example, a color digital image consisting of 1024xc3x971024 pixels. If the pixels are represented in the computer by three image planes of 8-bit numbers, the digital image would occupy over 1 megabyte of storage space.
The large amount of data required to represent a digital image in a computer can result in significant costs that are associated both with increased storage capacity requirements, and the computing resources and time required to transmit the data to another computing device. In order to reduce these costs, digital image compression techniques have been and are continuing to be developed.
Digital image compression techniques can generally be divided into two classes: lossless and lossy. In lossless compression, the digital image reconstructed after compression is identical, pixel by pixel, to the original image. A common lossless compression technique is the well known Lempel-Ziv-Welch (LZW) compression scheme. See, for example, U.S. Pat. No. 5,479,587. That Patent is incorporated herein by reference. Another lossless compression technique is described by the xe2x80x9cJoint Bi-level Image Experts Group Compression standardxe2x80x9d (JBIG).
In lossy compression, the reconstructed digital image may be somewhat degraded with respect to the original digital image in order to attain higher compression ratios than those of lossless procedures. One popular lossy compression scheme is referred to as xe2x80x9ctransform codingxe2x80x9d. See Baxes, G. A., Digital image Processing, Principles and Applications, pp 198-211, ISBN 0-471-00949-0 (1994). Those pages are incorporated herein by reference.
In general, transform encoding is accomplished by decomposing each image plane of a digital image into a set of two-dimensional blocks of pixel component values that define a sub-array of pixels. These blocks are typically small, such as 4xc3x974 or 8xc3x978 blocks of component values. Each block is then transformed into the frequency domain by use of a frequency transform. This reduces the block into a series of basis functions. It is noted that typically the first basis function is a constant scalar value. This is sometimes referred to as the xe2x80x9cDCxe2x80x9d component or alternatively as the xe2x80x9cDC coefficientxe2x80x9d for the transform. While in the frequency domain, the amount of data required to represent the block can be reduced by quantization. This is often accomplished by using criteria based on the visibility of each basis functions. After quantization, the amount of data representing the block can be even further reduced by using an entropy encoding (e.g., Huffman coding) technique.
A number of transform coding schemes have been developed. One widely used transform coding scheme has been standardized by the published and generally available works of the Joint Photographic Experts Group (JPEG). See generally, Pennebaker, W. B., and Mitchell, J. L., JPEG: Still Image Compression Standard, ISBN 0-442-01272-1 (1993). The JPEG compression standard in lossy mode makes use of the Discrete Cosine Transform (DCT). Like many transform coding schemes, the JPEG compression scheme is adjustable. That is to say that the number of frequency components discarded during quantization can be varied to produce variable compression ratios. Unfortunately, however, as the level of quantization increases to achieve higher compression ratios, image quality can be degraded significantly.
As just discussed, digital image compression techniques can be used to reduce the amount of data required to represent a digital image in a computer. These techniques can reduce the computing costs associated with storing and transmitting digital images. There are, however, significant costs that can be incurred in using these compression techniques. For example, there can be substantial system overhead and time required to perform the compression and decompression operations. In addition, there is a trade off between the use of lossy compression techniques and lossless compression techniques. In general, lossy compression can be used to achieve high compression ratios. Image quality, however, can be significantly degraded. Lossless compression, on the other hand, does not degrade image quality but usually results in relatively low compression ratios.
An apparatus for compressing a digital image comprising pixels having a first value and comprising a means for decomposing said digital image into a set of tiles; and a means for compressing each tile from said set of tiles, wherein said compressing means responsive to a binary tile from said set of tiles, said binary tile comprising pixels having a background value and pixels having one other value, to generate a first and an associated second set of data, said first set of data comprising spatial location information for substantially all pixels in said binary tile having said background value and said second set of data comprising data representative of a compressed second tile, each pixel in said second tile having said one other value.